import cn.hutool.core.collection.CollUtil;
import cn.hutool.core.util.RandomUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * @author zxs
 * @since 2021/6/16
 */
public class SkipList2 {

    private static final int MAX_LEVEL = 16;

    private Node head = new Node();
    private Random random = new Random();
    private int levelCount = 0;

    public void insert(int value) {
        int level = randomLevel();
        Node newNode = new Node();
        newNode.data = value;
        newNode.maxLevel = level;
        //初始化需要更新引用节点的数组
        Node[] update = new Node[level];
        for (int i = 0; i < level; i++) {
            update[i] = head;
        }
        //从头节点依次从上往下找到仅次于当前值的节点，放入更新数组中
        Node p = head;
        for (int i = level - 1; i >= 0; i--) {
            while (p.next[i] != null && p.next[i].data < value) {
                p = p.next[i];
            }
            update[i] = p;

        }

        //让待更新数组节点和新节点互相引用
        for (int i = 0; i < level; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
        //更新最大索引层数
        if (levelCount < level) {
            levelCount = level;
        }
    }

    public Node find(int value) {
        Node p = head;
        //从上向下找到最底层最接近value的节点
        int count = 0;
        for (int i = levelCount - 1; i >= 0; i--) {
            while (p.next[i] != null && p.next[i].data < value) {
                p = p.next[i];
                count++;
            }
        }
        //如果最底层的下一个节点是当前值，返回该节点，如果为空或不等，说明没有这个值的节点
        if (p.next[0] != null && p.next[0].data == value) {
            System.out.println(count);
            return p.next[0];
        } else {
            return null;
        }
    }

    public void remove(int value) {
        Node[] update = new Node[levelCount];
        Node p = head;
        //从上向下找到最底层最接近value的节点
        for (int i = levelCount - 1; i >= 0; i--) {
            while (p.next[i] != null && p.next[i].data < value) {
                p = p.next[i];
            }
            update[i] = p;
        }
        if (p.next[0] != null && p.next[0].data == value) {
            p = p.next[0];
            //更新节点引用
            for (int i = 0; i < p.maxLevel; i++) {
                update[i].next[i] = p.next[i];
            }
        }
    }

    public void print() {
        Node p = head;
        for (int i = levelCount - 1; i >= 0; i--) {
            while (p != null) {
                System.out.print(p.data+"   ");
                p = p.next[i];
            }
            System.out.println();
            p = head;
        }
    }

    private int randomLevel() {
        int level = 1;
        for (int i = 1; i < MAX_LEVEL; ++i) {
            if (random.nextInt() % 2 == 1) {
                level++;
            }
        }
        return level;
    }

    class Node {
        private int data = -1;
        private Node[] next = new Node[MAX_LEVEL];
        private int maxLevel;
        private int index;
    }

    public static void main(String[] args) {
        SkipList2 l = new SkipList2();
        List<Integer> data = new ArrayList<>();
        for (int i= 0;i<20;i++){
            data.add(RandomUtil.randomInt(30));
        }
        System.out.println(CollUtil.join(data,","));
        data.forEach(l::insert);
        //Arrays.asList(25,19,9,24,13,11,2,21,20,8,6,15,29,14).forEach(l::insert);
        l.print();
        System.out.println("--------------------");
        //l.remove(9);
        //l.print();
        l.find(24);
    }
}
